//二叉搜索树 左侧子节点放的是比父节点小的值  右侧子节点放的是比父节点大的值

class Node{
    constructor(element){
        this.left = null;
        this.right = null;
        this.element = element;
    }
}

class Tree{
    constructor(){
        this.root = null; //记录根节点
    }

    //插入一个节点
    insert(element){
        //1.创建节点
        let node = new Node(element);
        //2.判断插入的位置
        if(this.root === null){
            this.root = node;
        }else{
            this.insertNode(this.root,node);
        }
    }

    insertNode(rootNode,newNode){
        if(rootNode.element < newNode.element){
            //右边
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(rootNode.right,newNode);
            }
        }else{
            //左边
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(rootNode.left,newNode);
            }
        }
    }

    //获取最小值
    min(){
        return this.minNode(this.root);
    }

    minNode(rootNode){
        while(rootNode.left != null){
            rootNode = rootNode.left;
        }
        return rootNode
    }

    //最大值
    max(){
        return this.maxNode(this.root);
    }

    maxNode(rootNode){
        while(rootNode.right != null){
            rootNode = rootNode.right;
        }
        return rootNode
    }

    //搜索
    search(element){  //true false
        return this.searchNode(element,this.root)
    }

    searchNode(element,rootNode){
        //当前节点为空
        if(rootNode === null){
            return false
        }
        if(element < rootNode.element){
            //左边
            return this.searchNode(element,rootNode.left);
        }else if(element > rootNode.element){
            //右边
            return this.searchNode(element,rootNode.right);
        }else{
            //找到了
            return true
        }
    }

    //中序遍历
    inOrderTraverse(callback){
        this.inOrderTraverseNode(this.root,callback);
    }

    inOrderTraverseNode(node,callback){
        if(node != null){
            this.inOrderTraverseNode(node.left,callback);
            callback(node.element);
            this.inOrderTraverseNode(node.right,callback);
        }
    }

}

let tree = new Tree();

tree.insert(11);

tree.insert(7);

tree.insert(5);

tree.insert(15);

tree.insert(20);

console.log(tree.max());

console.log(tree.search(20))

let callback = (element) => {
    console.log(element)
}

tree.inOrderTraverse(callback)
